#!/usr/bin/env python
#encoding latin1

from grafo_nodo import *
from grafo import *
from pila import *

infinito = 9999999999999999999999999999999999999999999999999

ANTERIOR = 0
DISTANCIA = 1
"""
Encuentra el camino minimo desde un nodo base hacia cualquier nodo
del grafo mediante el algoritmo de Dijkstra
"""
"""
Esta es la primera version del algoritmo de Dijkstra que usamos
cuyos resultados no correspondian con los esperados a pesar 
de que la funcion cumple con su cometido.
"""
def dijkstra_resolve(grafo, nombre_nodo_base):
	solucion = dict()
	visitado = dict()
	mipila = pila()
	for nodo in grafo.keys():
		solucion[nodo] = {ANTERIOR : None, DISTANCIA : infinito}
		visitado[nodo] = False
	(solucion[nombre_nodo_base])[DISTANCIA] = 0
	mipila.apilar(nombre_nodo_base)
	while mipila.count > 0:
		nombre_nodo = mipila.desapilar()
		visitado[nombre_nodo] = True
		nodo = grafo[nombre_nodo]
		salientes = nodo.salidas
		for conexion in salientes.keys():
			dato = solucion[conexion]
			d = (solucion[nombre_nodo])[DISTANCIA] + salientes[conexion]
			if d < dato[DISTANCIA] and not visitado[conexion]:
				dato[DISTANCIA] = d
				dato[ANTERIOR] = nombre_nodo
				mipila.apilar(conexion)
	return solucion
"""
Esta es la version definitiva a usar en el trabajo practico.
"""
def camino_min(grafo, nombre_nodo_base):
	solucion = dict()
	en_espera = dict()
	mipila = pila()
	for nodo in grafo.keys():
		solucion[nodo] = {ANTERIOR : None, DISTANCIA : infinito}
		en_espera[nodo] = False
	solucion[nombre_nodo_base][DISTANCIA] = 0
	en_espera[nombre_nodo_base] = True
	mipila.apilar(nombre_nodo_base)
	while mipila.count > 0:
		nombre_nodo = mipila.desapilar()
		en_espera[nombre_nodo] = False
		nodo = grafo[nombre_nodo]
		salientes = nodo.salidas
		for conexion in salientes.keys():
			dato = solucion[conexion]
			d = (solucion[nombre_nodo])[DISTANCIA] + salientes[conexion]
			if d < dato[DISTANCIA]:
				dato[DISTANCIA] = d
				dato[ANTERIOR] = nombre_nodo
				if not en_espera[conexion]:
					mipila.apilar(conexion)
					en_espera[conexion] = True
	return solucion
"""
Solucion es lo que devuelve camino_min.
Se devuelve una lista con los nombres de los nodos a recorrer,
desde el nodo inicial hasta nodo_a_llegar
"""
def Generar_recorrido(solucion, nodo_a_llegar):

	recorrido = list()
	distancia = int(solucion[nodo_a_llegar][DISTANCIA])
	recorrido.append(distancia)
	nodo_anterior = nodo_a_llegar
	while nodo_anterior is not None:
		nodo = nodo_anterior
		recorrido.insert(1,nodo)
		nodo = solucion[nodo]
		nodo_anterior = nodo[ANTERIOR]
	return recorrido
